Kích thước và đặc tính của những chiếc Panzerschiffe bị giới hạn đáng kể bởi Hiệp ước Versailles, vốn chỉ cho phép Đức đóng tàu chiến không vượt quá trọng lượng choán nước 10.000 tấn. Một số cải tiến kỹ thuật đã được áp dụng để chế tạo một con tàu chiến chắc chắn trong tải trọng bị giới hạn, bao gồm việc áp dụng rộng rãi kỹ thuật hàn để kết nối các thành phần của lườn tàu (thay cho việc dùng đinh tán ghép các tấm thép chồng lên nhau, vốn là tiêu chuẩn vào thời đó), và động cơ diesel cho hệ thống động lực. Ngay cả như vậy, Deutschland vẫn nặng hơn giới hạn 2.000 tấn, cho dù vì những lý do chính trị, trọng lượng được công bố của nó luôn được nêu là 10.000 tấn trong giới hạn của Hiệp ước.

Hai chiếc tương tự khác trong lớp tàu của nó, Admiral Graf Spee và Admiral Scheer. Vì Deutschland là chiếc dẫn đầu trong lớp, nó kém hiện đại nhất, và không có được kiểu dáng đặc trưng một tháp chỉ huy và cầu tàu cao cùng các cột ăn-ten như của Admiral Scheer và Admiral Graf Spee, làm cho hai chiếc tàu chiến sau này có kiểu dáng bên ngoài giống như những thiết giáp hạm hiện đại.

Deutschland được đặt lườn vào tháng 2 năm 1929 tại xưởng tàu của hãng Deutsche Werke ở Kiel; và được hạ thủy vào tháng 5 năm 1931 có sự hiện diện của Tổng thống Đức Paul von Hindenburg. Nó hoàn tất việc trang bị vào cuối năm 1931 và thực hiện chuyến hải hành đầu tiên vào tháng 5 năm 1932.